package com.le.basic.Sort;

/**
 * 题目
 * 给定一个数组arr和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
 * 要求额外空间复杂度O(1)，时间复杂度O(N)
 */
public class Code_06_arrayPartition {

    public static void partition(int[] arr, int num){
        if (arr == null || arr.length < 2 ){
            return;
        }
        int less = -1;
        int cur = 0;
        int more = arr.length;
        while (cur < more){
            if (arr[cur] <= num){ // 如果当前数小于num,则less加一位置与当前数交换
                swap(arr,++less,cur++);
            }else { // 如果当前数大于于num,则 more-1位置与当前数交换
                swap(arr, --more,cur);
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] test = {1,3,4,2,5};
        partition(test,2);
        for (int i : test) {
            System.out.print(i + "  ");
        }
    }
}
